Combinatorial design

Combinatorial design theory is the part of combinatorial mathematics that deals with the existence and construction of systems of finite sets whose intersections have specified numerical properties.

For instance, a balanced incomplete block design (usually called for short a block design) is a collection B of b subsets (called blocks) of a finite set X of v elements, such that any element of X is contained in the same number r of blocks, every block has the same number k of elements, and any two blocks have the same number λ of common elements. For example, if λ = 1 and b = v, we have a projective plane: X is the point set of the plane and the blocks are the lines.

A spherical design is a finite set X of points in a (d − 1)-dimensional sphere such that, for some integer t, the average value on X of every polynomial

f(x_1, \ldots, x_d)\

of total degree at most t is equal to the average value of f on the whole sphere, i.e., the integral of f divided by the area of the sphere.

Combinatorial design theory is applied to the design of experiments. Some of the basic theory of combinatorial designs originated in Ronald Fisher's work on design of experiments.

Contents

Example

Given a certain number n of people, is it possible to assign them to sets so that each person is in at least one set, each pair of people is in exactly one set together, every two sets have exactly one person in common, and no set contains everyone, all but one person, or exactly one person? The answer depends on n.

This has a solution only if n has the form q2 + q + 1. It is less simple to prove that a solution exists if q is a prime power. It is conjectured that these are the only solutions. It has been further shown that if a solution exists for q congruent to 1 or 2 mod 4, then q is a sum of two square numbers. This last result, the Bruck–Ryser theorem, is proved by a combination of constructive methods based on finite fields and an application of quadratic forms.

When such a structure does exist, it is called a finite projective plane; thus showing how finite geometry and combinatorics intersect.

Probabilistic combinatorics

Main article: Probabilistic combinatorics

In probabilistic combinatorics, the questions are of the following type: what is the probability of a certain property for a random discrete object, such as a random graph. For instance, what is the average number of triangles in a random graph? Probabilistic methods are also used to determine the existence of combinatorial objects with certain prescribed properties (for which explicit examples might be difficult to find), simply by observing that the probability of randomly selecting an object with those properties is greater than 0. This approach proved highly effective in applications to extremal combinatorics and graph theory. A closely related area is the study of finite Markov chains, especially on combinatorial objects. Here again probabilistic tools are used to estimate the mixing time.

Often associated with Paul Erdős, who did the pioneer work on the subject, probabilistic combinatorics was traditionally viewed as a set of tools to study problems in other parts of combinatorics. However, with the growth of applications to analysis of algorithms in computer science, as well as classical probability, additive and probabilistic number theory, the area recently grew to become an independent field of combinatorics.

See also

Bibliography

External links